package 剑指Offer._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/7/2 18:51
 * 数组中重复的数字
 * 算法：数组
 * 因为数组长度为 n，并且数字的范围为 0 ~ n - 1
 * 所以可以按照下标标记元素
 * 将已经遍历过的数字对应下标的元素置为负数
 * 如果遍历到的元素为负数，则该数字已经出现过了
 */
public class _03 {

    public int findRepeatNumber(int[] nums) {
        // 0 的负数还是 0，不容易判断，所以要排除 0
        for (int i = 0; i < nums.length; i++) ++nums[i];
        for (int i = 0; i < nums.length; i++) {
            int newIdx = Math.abs(nums[i]) - 1;
            if (nums[newIdx] < 0) return newIdx;
            nums[newIdx] *= -1;
        }
        return -1;
    }

}
